package datastruct.树.线段树;

import javafx.util.Pair;

import java.util.Comparator;
import java.util.List;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * 线段树模板
 * @param <V> 节点值类型
 */
public class SegmentTree<V> {
    protected List<Pair<Integer,V>> originIndexValueList;
    AbstractNode<V> root;

    // 不想反射啊!
    public void acceptRoot(AbstractNode<V> root) {
        this.root = root;
    }

    //region private
    private <N extends AbstractNode,I,O> O _visit(N now, AbstractNode.Visitable<N,I,O> visitor, I input, int left, int right) {
        // 完全在区间内
        if (now.l >= left && now.r <= right) {
            return visitor.inRange(now,input);
        }
        // 不在区间内，提供一个可合并的空值
        if(now.l>=right||left>=now.r) {
            return visitor.notInRange(now,input);
        }

        return visitor.merge(now,
                _visit((N) now.lson, visitor,input,left,right),
                _visit((N) now.rson, visitor,input,left,right));
    }

    protected <N extends AbstractNode> N build(int l, int r) {
        if(r-l==1) {
            return (N) root.supplierLeaf(l,originIndexValueList.get(l).getValue());
        } else {
            int mid = (l+r)>>1;
            AbstractNode<V> vAbstractNode = root.supplierNotLeaf(l, r);
            vAbstractNode.lson = build(l,mid);
            vAbstractNode.rson = build(mid,r);
            return (N) vAbstractNode.updateNotLeaf();
        }
    }
    //endregion

    //region static
    static <T> int lower_search(int left, int right, T aim, Function<Integer, T> indexToObject, Comparator<T> comparator) {
        while (left < right) {
            int mid = (left + right) >> 1;
            if (comparator.compare(indexToObject.apply(mid), aim) < 0) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    static <T> int upper_search(int left, int right, T aim, Function<Integer, T> indexToObject, Comparator<T> comparator) {
        while (left < right) {
            int mid = (left + right) >> 1;
            if (comparator.compare(indexToObject.apply(mid), aim) <= 0) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    static <A,B> List<Pair<A,B>> zip(List<A> aList,List<B> bList ) {
        if(aList.size()!=bList.size()) {
            throw new RuntimeException(String.format("两个列表的大小必须相等,aList size:%s,bList size:%s", aList,bList));
        }
        return IntStream.range(0,aList.size()).mapToObj(i->new Pair<>(aList.get(i),bList.get(i))).collect(Collectors.toList());
    }
    //endregion

    //region public
    public <N extends AbstractNode,I,O> O visit(AbstractNode.Visitable<N,I,O> visitor, I input, int left, int right) {
        int l = lower_search(0,originIndexValueList.size(),left,i->originIndexValueList.get(i).getKey(),Integer::compare);
        int r = upper_search(0,originIndexValueList.size(),right,i->originIndexValueList.get(i).getKey(),Integer::compare);
        if(l>=r) {
//            return visitor.notInRange(self(),input);
            return visitor.notInRange(root.self(),input);
        }
        return _visit(root.self(), visitor,input,l,r);
    }

    public <O> O query(AbstractNode.Visitable<? extends AbstractNode,Void,O> visitor, int left, int right) {
        return visit(visitor,null,left,right);
    }

    public <I> void operate(AbstractNode.Visitable<? extends AbstractNode,I,Void> visitor, I input, int left, int right) {
        visit(visitor,input,left,right);
    }

    public void treeBuild(List<Integer> indexList,List<V> valueList){
        treeBuild(zip(indexList,valueList));
    }

    public void treeBuild(List<Pair<Integer, V>> indexValue){
        // 1. 将传入的数据按索引排序

        this.originIndexValueList = indexValue.stream().sorted(Comparator.comparing(Pair::getKey)).collect(Collectors.toList());
        // 2. 构建树
        build(0,indexValue.size());
    }
    //endregion

    public abstract static class AbstractNode<V> {

        //region private
        //endregion

        //region protect
        protected int l;
        protected int r;
        public V value;
        protected AbstractNode<V> lson;
        protected AbstractNode<V> rson;

        //region 构造相关
        protected abstract AbstractNode<V> supplier();
        // 子节点完成构造或者更新过，父节点的更新操作,此时父节点的左右儿子已经赋值过
        protected abstract AbstractNode<V> updateNotLeaf();
        protected abstract <T extends AbstractNode> T self();
        // 提供一个非叶子节点，
        protected AbstractNode<V> supplierNotLeaf(int l,int r) {
            AbstractNode<V> supplier = supplier();
            supplier.l=l;
            supplier.r=r;
            return supplier;
        }
        protected AbstractNode<V> supplierLeaf(int pos,V v) {
            AbstractNode<V> supplier = supplier();
            supplier.l = pos;
            supplier.r = pos+1;
            supplier.value = v;
            return supplier;
        }
        //endregion

        protected <T> void reBuild(AbstractNode<T> node, T t) {
            if(node.lson==null) {
                node.value = t;
            } else {
                reBuild(node.lson,t);
                reBuild(node.rson,t);
                node.updateNotLeaf();
            }
        }

        protected interface Visitable<N extends AbstractNode,I,O> {
            O inRange(N node,I input);
            O notInRange(N node,I input);
            O merge(N node,O leftOutput,O rightOutput);
        }
        //endregion
    }


}
